Міністерство освіти України
Національний університет «Львівська політехніка»
Кафедра автоматизованих систем управління
ІМІТАЦІЙНЕ МОДЕЛЮВАННЯ ПРОЦЕСУ
ФУНКЦІОНУВАННЯ СКІНЧЕНОГО ДИСКРЕТНОГО
СТОХАСТИЧНОГО АВТОМАТА
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи
з дисципліни "Моделювання систем"
для студентів базового напрямку 6.050101 “Комп’ютерні науки”
Львів 2011
Імітаційне моделювання процесу функціонування скінченого дискретного стохастиного автомата. Методичні вказівки до лабораторної роботи з дисципліни “Моделювання систем” для студентів базового напрямку 6.050101 “Комп’ютерні науки”/ Укладач: к.т.н., доцент кафедри АСУ Кузьмін О.В. – Львів, Національний університет “Львівська політехніка”, 9 с.
Укладач: Кузьмін Олександр Васильович
Відповідальний за випуск: к.т.н., доцент Шпак З.Я.
Рецензент: д.т.н., професор Різник В.В.
Методичні вказівки затверджено на засіданні кафедри АСУ
Протокол № 2-2011/2012 від 20 вересня 2011 р.
Мета роботи - вивчити процес функціонування дискретного скінченого стохастичного автомата та знайти його ймовірностні характеристики за даними експерименту.
І. ОСНОВНІ ПОЛОЖЕННЯ.
Математичні моделі автоматів вивчаються у розділі теоретичної кібернетики - теорії автоматів. Основним у цій теорії є представлення системи у вигляді автомата, який опрацьовує дискретну інформацію та змінює свої внутрішні стани в допустимі моменти часу. Автомат - це деякий пристрій, на вхід якого поступають вхідні сигнали, під дією яких залежно від внутрішнього стану на виході формуються вихідні сигнали, і відбувається перехід в інший внутрішній стан. Скінченим називається автомат, у якого множини внутрішніх ста нів, вхідних та вихідних сигналів скінченні. Скінченний автомат, харак теризується скінченими множинами вхідних сигналів X (вхідний алфа віт), вихідних сигналів Y (вихідний алфавіт), станів Z (алфавіт станів), функціями виходів та переходів.
1.1. Дискретні детерміновані автомати.
Дискретні детерміновані автомати (F-схеми) описуються у вигляді шістки , де X, Y, Z - множини відпо відно вхідних, вихідних сигналів та станів, Z0 - початковий стан, , - відповідно функції переходів та виходів.
Автомат, який описується F-схемою, функціонує в дискретному авто матному часі. У момент часу ti автомат знаходиться в стані , сприймає на вході сигнал , генерує на виході сигнал , і після цього переходить у стан , . Описана послідовність дій відбувається миттєво.
Таким чином реалізується деяке відображення символів вхідного алфа віту в множину символів вихідного.
Автомат Мілі описується за допомогою таких функцій переходів та виходів:
(1)
Для автомата Мура функції виходів та переходів мають вигляд
(2)
За характером відліку дискретного часу автомати поділяються на синхронні та асинхронні. В синхронних автоматах моменти часу дії вхідних сигналів синхронізуються сигналом повної частоти (наприклад, ЕОМ). Асинхронний автомат може сприймати вхідні сигнали в довільні моменти часу (наприклад, автомат для продажу газет та журналів).
Функціонування F-автомата може бути описане одним з трьох способів: табличним, графічним та матричним.
Табличний спосіб вимагає побудови таблиць переходів та виходів (табл. 1, 2).
Таблиця 1
Таблиця переходів F-автомата
X
Z
...
...
Таблиця 2 .
Таблиця виходів F -автомата
X
Z
...
...
У графовому представленні F-автомата, вершини графу відповідають станам автомата, а дуги, які їх з’єднують, тим чи іншим переходам автомата із стану в стан. Якщо вхідний сигнал, Хк викликає перехід з стану Zi в стан Zj, то дуга, яка з’єднує Zj з Zi, позначається Хk. Для задання функції виходів дуги графа необхідно помітити вихідними сигналами. Для автомата Мілі розмітка здійснюється так: якщо вхідний сигнал Хk діє на автомат, що знаходиться в стані Zi, то дугу, яка виходить з Zi і помічена Хk, додатково помічають вихідним сигналом . Для автомата Мура розмітка здійснюється так: якщо вхідний сигнал Xk діє на автомат,...
